/**
 * Author: Brent Myers
 * Time-stamp: <2008-07-23 21:00:25 bam>
 * 
 * Templated Performance Tests
 * 
 */

#include <boost/test/unit_test.hpp>
#include <boost/test/test_case_template.hpp>

#include <boost/mpl/list.hpp>

#include "src/genhash.h"
#include "src/Chaining.h"
#include "src/LinearProbe.h"
#include "src/ModuloHash.h"
#include "src/BitmaskHash.h"

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
#include <string>
#include <boost/assign/std/vector.hpp>
#include <boost/foreach.hpp>
#include <iostream>
#include <map>
#include <cfloat>

using std::map;

using std::cout;
using std::endl;
using std::string;

using boost::unit_test::test_suite;

using namespace genhash;

using boost::mt19937;
using boost::uniform_int;
using boost::uniform_real;
using boost::variate_generator;
using boost::timer;

using boost::lexical_cast;

using namespace boost::assign;

BOOST_TEST_CASE_TEMPLATE_FUNCTION( insert1 , HT )
{
	HT ht;
	mt19937 rand;
	uniform_int<> dist(0, 10000);
	double sum_elapsed = 0.0;
	variate_generator<boost::mt19937&, boost::uniform_int<> > die(rand, dist);
	timer t;
	for(int i = 0; i < 10000; ++i)
	{
		int x = die();
		int y = die();
		ht[x] = y;
	}
	sum_elapsed = t.elapsed();
	cout << "time for 10000 inserts (seconds): " << sum_elapsed << endl;
}

BOOST_TEST_CASE_TEMPLATE_FUNCTION( find_string , HT )
{
	mt19937 rand;
	uniform_real<> dist(INT_MIN, INT_MAX );
	variate_generator<boost::mt19937&, boost::uniform_real<> > die(rand, dist);

	vector<float> load_ratios;
	load_ratios += 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0;

	BOOST_FOREACH(float ratio, load_ratios)
	{
		HT ht;
		double sum_elapsed = 0.0;
		size_t n_elements = ratio * float(ht.max_size());
		map<string, int> inserted_keys;
		for(size_t i = 0; i < n_elements; )
		{
			string x = lexical_cast<string>(die());
			int y = die();
			pair<map<string, int>::iterator, bool> ret = inserted_keys.insert(make_pair(x,y));
			if(ret.second)
			{
				ht[x] = y;
				++i;
			}
		}
		timer t;
		BOOST_FOREACH(typename HT::value_type v, inserted_keys)
		{
			typename HT::iterator it = ht.find(v.first);
			//BOOST_CHECK_EQUAL(it->second, v.second);
		}
		sum_elapsed = t.elapsed();
		cout << "time per find in us at load=" << ratio << " (" << n_elements << ") elements: " 
			 << (sum_elapsed * 1000000.0) / n_elements << endl;
	}
}

BOOST_TEST_CASE_TEMPLATE_FUNCTION( find_int , HT )
{
	mt19937 rand;
	uniform_int<> dist(INT_MIN, INT_MAX);
	variate_generator<boost::mt19937&, boost::uniform_int<> > die(rand, dist);

	vector<float> load_ratios;
	load_ratios += 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0;

	BOOST_FOREACH(float ratio, load_ratios)
	{
		HT ht;
		double sum_elapsed = 0.0;
		size_t n_elements = ratio * float(ht.max_size());
		map<int, int> inserted_keys;
		for(size_t i = 0; i < n_elements; )
		{
			int x = die();
			int y = die();
			pair<map<int, int>::iterator, bool> ret = inserted_keys.insert(make_pair(x,y));
			if(ret.second)
			{
				ht[x] = y;
				++i;
			}
		}
		timer t;
		BOOST_FOREACH(typename HT::value_type v, inserted_keys)
		{
			typename HT::iterator it = ht.find(v.first);
			//BOOST_CHECK_EQUAL(it->second, v.second);
		}
		sum_elapsed = t.elapsed();
		cout << "time per find in ms at load=" << ratio << " (" << n_elements << ") elements: " 
			 << (sum_elapsed * 1000.0) / n_elements << endl;
	}
}


struct Config1 
{
	enum { max_size = 100000 };
	typedef int KeyType;
	typedef int DataType;
	typedef SimpleModuloHash<Config1> HashFn;
	typedef Chaining<Config1> CollisionStrategy;
	typedef Hashtable<CollisionStrategy> RET;
};
typedef Config1::RET HT1;

struct Config2 
{
	enum { max_size = 100000 };
	typedef int KeyType;
	typedef int DataType;
	typedef SimpleModuloHash<Config2> HashFn;
	typedef LinearProbe<Config2> CollisionStrategy;
	typedef Hashtable<CollisionStrategy> RET;
};
typedef Config2::RET HT2;

struct Config3
{
	enum { max_size = 100000 };
	typedef string KeyType;
	typedef int DataType;
	typedef SimpleModuloHash<Config3> HashFn;
	typedef Chaining<Config3> CollisionStrategy;
	typedef Hashtable<CollisionStrategy> RET;
};
typedef Config3::RET HT3;

struct Config4
{
	enum { max_size = 100000 };
	typedef string KeyType;
	typedef int DataType;
	typedef SimpleModuloHash<Config4> HashFn;
	typedef LinearProbe<Config4> CollisionStrategy;
	typedef Hashtable<CollisionStrategy> RET;
};
typedef Config4::RET HT4;

BOOST_AUTO_TEST_CASE(performance)
{
	test_suite* test = BOOST_TEST_SUITE( "Hashtable Performance Tests" );
	typedef boost::mpl::list<HT1, HT2> int_hts;
	typedef boost::mpl::list<HT3, HT4> string_hts;

    test->add( BOOST_TEST_CASE_TEMPLATE( insert1, int_hts ) );
    test->add( BOOST_TEST_CASE_TEMPLATE( find_int, int_hts ) );
 	test->add( BOOST_TEST_CASE_TEMPLATE( find_string, string_hts ) );

	boost::unit_test::framework::run( test );
}
